
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int>ret;
        if (root == nullptr)
            return ret;
        queue<TreeNode*>st;
        st.push(root);
        while (st.size())
        {
            int sz = st.size();
            int maxp = INT_MIN;
            for (int i = 0; i < sz; i++)
            {
                auto a = st.front();
                st.pop();
                maxp = max(maxp, a->val);
                if (a->left)st.push(a->left);
                if (a->right)st.push(a->right);



            }
            ret.push_back(maxp);





        }

        return ret;

    }
};


class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if (root == nullptr)
            return ret;
        queue<Node*>st;
        st.push(root);
        while (st.size())
        {
            int sz = st.size();
            vector<int>path;
            for (int i = 0; i < sz; i++)
            {
                auto a = st.front();
                st.pop();
                path.push_back(a->val);
                for (auto e : a->children)
                    if (e)st.push(e);
            }
            ret.push_back(path);







        }
        return ret;








    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
typedef pair<TreeNode*, int> PLL;
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        vector<pair<TreeNode*, unsigned int>>st;
        st.push_back({ root,1 });
        unsigned int ret = 0;
        while (st.size())
        {

            auto& [x1, y1] = st[0];
            auto& [x2, y2] = st.back();
            ret = max(ret, y2 - y1 + 1);
            vector<pair<TreeNode*, unsigned int>>tmp;
            for (auto [a, b] : st)
            {
                if (a->left)tmp.push_back({ a->left,b * 2 });
                if (a->right)tmp.push_back({ a->right,b * 2 + 1 });
            }
            st = tmp;

        }
        return ret;









    }
}; class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (auto e : s1)
        {
            hash1[e - 'a']++;
        }
        for (auto e : s2)
        {
            hash2[e - 'a']++;
        }

        for (int i = 0; i < 26; i++)
        {
            if (hash1[i] != hash2[i])
                return false;
        }

        return true;









    }
}; class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int>st;
        vector<int>result;
        for (int i = 0; i < nums.size(); i++)
        {

            int x = target - nums[i];
            if (st.count(x))
            {

                return { i,st[x] };

            }
            st[nums[i]] = i;







        }


        return { -1,-1 };





    }
}; class Solution {
public:
    bool canConstruct(string r, string m) {
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (auto e : r)
        {
            hash1[e - 'a']++;
        }
        for (auto e : m)
        {
            hash2[e - 'a']++;
        }
        for (int i = 0; i < 26; i++)
        {
            if (hash1[i])
            {
                if (hash1[i] > hash2[i])
                    return false;






            }






        }
        return true;








    }
};